The present invention relates generally to computing systems and more particularly to methods and apparatus for correcting the orientation of skewed graphical objects.
A conventional scanner or other optical recognition device can be used to produce a graphical representation (a digital version) of an image, text, photograph or picture that can in turn be displayed on a monitor screen. Conventional scanners digitize an image using a scanning device. The scanning device can be of the form of an optical scanner. An optical scanner is an input device that allows a user to take an image or text and render it as a digital image. The image can then be converted in to a graphics file or text file using optical character recognition software. Material scanned can, in turn, be faxed, sent by electronic mail, printed or edited.
Conventional scanners receive data in numerous ways. A flatbed scanner includes a glass scanning surface on which a document can be placed for scanning. A sheetfeed scanner receives hard copies of a document at an input port and includes a feeding mechanism for guiding the document through the device. A handheld scanner requires a user to move a scanning window across a document, where the scanning window is typically only a few inches wide. In each of these type of conventional scanning devices, the graphics produced can be skewed. Skew is defined as the angular or longitudinal deviation of an object from a specified reference. For a scanning device, the reference can be thought of as the original background of the document. After scanning, the objects present on the document may appear skewed from their original orientation on the document. Skewing can result from a slight rotation of the document on the scanning surface, improper feeding by a feed mechanism, or movement at an improper angle when using a handheld scanner.
Conventional computing systems can provide solutions for deskewing a graphical object. One method deskews the graphical object by transferring each pixel in the graphical object to a new position. Other methods use interpolation, including both bicubic and linear interpolation, to transfer pixels to new positions. Each of these methods results in intensive calculations to perform the deskewing process.
In general, in one aspect, the invention features a method of processing a source raster representation of an image. The source raster representation of the image has an orientation relative to the source raster. The method includes partitioning the source raster into blocks of pixels based on the orientation. For each block of pixels, a destination location in a destination raster is calculated from the orientation. Thereafter, blocks of pixels are transferred to the respective calculated destination locations in the destination raster.
The step of partitioning the source raster into blocks of pixels includes obtaining a height and a width of the source raster measured in pixels, calculating a number of columns from the width of the source raster and the orientation, calculating a number of rows from the height of the source raster and the orientation, and determining the sizes of the blocks of pixels from the width of the source raster, the height of the source raster, the number of rows, and the number of columns.
The step of calculating a destination location for a block of pixels includes calculating a displacement for each block of pixels based on the orientation of the source raster representation relative to the source raster, and adding the displacement to the original location of the respective block of pixels. Each block of pixels is transferred by copying the block of pixels to the destination location in the destination raster with a block transfer operation.
The method further includes finding a gap pixel in the destination raster between two blocks of pixels copied from the source raster, and determining a value for the gap pixel.
Preferred embodiments of the invention can include one or more of the following features. The value for each gap pixel is found by calculating a source pixel location in the source raster corresponding to the gap pixel location, and determining the value for the gap pixel from the value of the corresponding source pixel. The source raster representation of the image is rotated or skewed relative to the source raster.
Aspects of the invention can include one or more of the following advantages. The invention allows for a significant decrease in the number of calculations needed to obtain a slightly rotated raster image. The number of calculations needed to obtain a rotated raster image depends on the angle of rotation. For example, the smaller the angle of rotation, the larger the sizes of the blocks of pixels which result in a smaller number of calculations needed.
Other features and advantages of the invention will become apparent from the description, the drawings, and the claims.